package com.formula.datastructure.exam.graph.mst;

import com.formula.datastructure.exercise.graph.undirect.ListEdge;
import com.formula.datastructure.exercise.graph.undirect.ListGraph;
import com.formula.datastructure.exercise.graph.undirect.ListVertex;

public class Kruskal {

    private int[] root;

    public ListEdge[] getMST(ListGraph graph) {
        int N = graph.vertexSize();

        root = new int[N];

        ListEdge[] result = new ListEdge[N - 1];

        ListEdge[] edges = sort(graph.egdgList);

        for (int i = 0; i < N; i++) {
            root[i] = i;
        }

        int count = 0;

        for (int i = 0; i < edges.length; i++) {
            int a = getRoot(edges[i].fromIdx);
            int b = getRoot(edges[i].toIdx);

            if (a != b) {
                result[count++] = edges[i];
                root[edges[i].fromIdx] = edges[i].toIdx;
            }

            if (count >= N - 1) {
                break;
            }
        }

        return result;
    }

    int getRoot(int idx) {
        while (idx != root[idx]) {
            idx = root[idx];
        }
        return idx;
    }

    ListEdge[] sort(ListEdge[] edges) {
        int N = edges.length;
        int flag = 1;
        for (int i = 0; i < 9; i++) {
            if (flag == 0) {
                break;
            }
            flag = 0;
            ListEdge temp;
            for (int j = 0; j < 9 - i - 1; j++) {
                if (edges[j + 1].weight < edges[j].weight) {
                    flag = 1;
                    temp = edges[j + 1];
                    edges[j + 1] = edges[j];
                    edges[j] = temp;
                }
            }
        }
        return edges;
    }

    public static void main(String[] args) {
        testListGraph();
    }

    private static void testListGraph() {
        ListGraph graph = new ListGraph();
        ListVertex A = new ListVertex("A");
        ListVertex B = new ListVertex("B");
        ListVertex C = new ListVertex("C");
        ListVertex D = new ListVertex("D");
        ListVertex E = new ListVertex("E");
        ListVertex F = new ListVertex("F");

        ListEdge edge1 = new ListEdge(0, 1, 5);
        ListEdge edge2 = new ListEdge(0, 3, 9);
        A.addEdge(edge1);
        A.addEdge(edge2);

        ListEdge edge3 = new ListEdge(1, 2, 2);
        ListEdge edge4 = new ListEdge(1, 3, 10);
        B.addEdge(edge3);
        B.addEdge(edge4);

        ListEdge edge5 = new ListEdge(2, 4, 8);
        ListEdge edge6 = new ListEdge(2, 5, 7);
        C.addEdge(edge5);
        C.addEdge(edge6);

        ListEdge edge7 = new ListEdge(3, 4, 4);
        D.addEdge(edge7);


        ListEdge edge8 = new ListEdge(4, 5, 7);
        E.addEdge(edge8);

        ListEdge edge9 = new ListEdge(5, 1, 6);
        F.addEdge(edge9);

        graph.insertVex(A);
        graph.insertVex(B);
        graph.insertVex(C);
        graph.insertVex(D);
        graph.insertVex(E);
        graph.insertVex(F);

        Kruskal kruskal = new Kruskal();
        ListEdge[] result = kruskal.getMST(graph);
        System.out.println();
    }
}
